public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // System.out.println(test.numTrees(3));

        int[] testArr = new int[] {1,2,3,7,8,9,12,46,95};
        System.out.println(test.search(testArr, 11));
    }

    public int numTrees(int n) {
        /**
         * 不同的二叉搜索树
         * 状态表示：
         *  dp[i]表示有i个节点时，互不相同的二叉搜索树的个数
         * 状态转移方程：
         *  由于二叉搜索树通过变换不同的根节点时会呈现出不同的形状，因此我们需要对每个节点进行遍历
         *  可以通过左右子树不同二叉搜索树的个数来确定i的个数，这就是一个简单的排列组合问题
         *  假设左边有3，右边有2，则当前根节点的不同数就有2*3=6
         *  故得：dp[i] += dp[j-1] * dp[i-j];
         * 初始化：
         *  当以1或者n节点为根节点时，会出现一边子树没有节点，此时所有组合都为另一子树的组合
         *  为了使组合有效，我们将空树也看做一个二叉搜索树
         *  故使用虚拟位置法进行初始化，并将虚拟节点值赋值为1
         *  dp[0] = 1;
         * 填表顺序：
         *  从左到右
         * 返回值：
         *  return dp[n];
         * */
        // 1 创建dp表
        int[] dp = new int[n+1];
        // 2 初始化
        dp[0] = 1;
        // 3 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        // 4 返回值
        return dp[n];
    }

    public int search(int[] nums, int target) {
        /**
         * 二分查找
         * */
        // 1 定义待查找数组的左右边界
        int n = nums.length;
        int left = 0;
        int right = n-1;

        // 2 进入循环
        while(left <= right) {
            // -1 找到重点
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else if(target > nums[mid]) {
                left = mid + 1;
            }
        }

        // 3
        return -1;
    }
}
